The present invention relates to a communication control apparatus and to a method for determining the next transfer route for a packet received by way of its destination address and, more particularly, to a communication control for improving the efficiency in detecting a mask prefix.
In an IP (Internet Protocol) such as IPv4 (Internet Protocol Version 4), when communicating beyond a LAN (local area network), a destination IP address is included in the protocol sent to the router, which is then transferred by the router to establish communication with a target address. In a router product, such as a network router and an L3 switch, a system is capable of supporting more than one hundred thousand IP addresses, and also support a large plurality of servers and clients. However, when identifying an appropriate transfer destination port from the IP addresses, the system has to search all the IP addresses it holds to find the transfer destination port corresponding to the IP address.
Terminology
Techniques known in the art and underlying concepts in the IP address search field will be described hereinafter.
Router is defined as a device for transferring the protocol to an appropriate transfer destination based on the destination IP address information on the protocol sent thereto.
IP address structure. An IP address of IPv4 which is based on a CIDR (Classless Inter-Domain Routing) configuration consisting of a total of 32 bits reserved for the prefix and the host address. The boundary varies by 1 bit and differs according to the IP addresses.
Routing table. It is based on fixed routing information and on the routing information obtained from a protocol such as RIP (Routing Information Protocol) and OSPF (Open Shortest Path First). The router creates a routing table, i.e., a database using a prefix as a key (also referred to as “a network address” in the router). The prefix contains what has been aggregated. “To aggregate” refers to replacing multiple entries having a prefix, the upper bits thereof being common and directed to the same destination by way of a prefix entry having a shorter mask.
The router searches the routing table based on the destination IP address of the protocol to be transferred in order to obtain corresponding routing information, and transfers the protocol based on the routing information. The prefix is used as the search key for the routing table. The prefix, however, has a variable length, and the mask information is not included in the protocol. Thus, an entry with the longest prefix from the matching prefixes in the routing table is used.
The operation of an IPv4 router is known in the art. A method for sequentially searching a Patricia Tree and accelerating a field thereof using CAM (content-addressable memory) and the like, are utilized in the search process based on the mask having a variable length. By contrast, in Japan Published Unexamined Patent Application No. 2000-349811, it is disclosed that in order to simplify a hardware device for resolving the network address, the destination address is divided by a predetermined number of bits starting from the most significant bit (MSB), and having the divided field to be associated with nodes in the tree structure in a manner such that the lower divided field becomes the node at a lower hierarchy of the tree structure. Relay nodes and boundary nodes that do not correspond to the routing information are set to route nodes corresponding to the routing information.